Range coding in reference “Range_encoding”—Wikipedia, the free encyclopedia URL: http://en.wikipedia.org/wiki/Range_encoding (accessed Aug. 19, 2015) is used widely in situations where data compression is required, for example in video coding, image coding, audio coding, and data coding.
In overview, in range coding, probabilities of occurrences of symbols present in a data set that is to be encoded at an encoder have to be known, otherwise a compression efficiency of a range coding method utilized in the encoder suffers greatly. Each symbol present in the data set has an associated probability of occurrence, which defines a corresponding “range” during encoding of the data set; larger the probability of occurrence, larger is the range. When symbols in the data set are encoded in the encoder, the range is updated according to the probability of the encoded symbol. If the range becomes small enough, the encoder employing range encoding emits a byte and increases the range. Thus, with the more common symbols, the range decreases slowly and more symbols can be coded before a byte is emitted. Closer the probability of a symbol being coded is to an actual probability of the symbol at the time of coding, better is the coding efficiency of range coding.
Moreover, contemporary range coding is effective for coding large data sets, where probabilities of different possible symbols present in the large data sets are known. Usually, the probabilities are predetermined or delivered, for example by employing methods as described in a published UK patent document [GB2523348A or GB2523347A, for an entire data set to be coded for generating corresponding encoded data. Such an approach represents an efficient method, if different symbols always occur with similar frequencies within the large data set, and are uniformly distributed in the large data set.
However, in practice, some symbols are more common, for example, at a beginning of a data set to be encoded, and some symbols are more common at an end of the data set. In such cases, a set of fixed predetermined probabilities will not provide an optimal coding efficiency in an encoder. Thus, it is conventionally better to modify probabilities for the symbols present in the data set when encoding the data set to generate corresponding encoded data.
It will be appreciated from publicly-accessible patent and technical literature that there exists a lot of different range coding methods. Some of the known implementations use contextual information to modify the probabilities, whereas some other known implementations modify the predetermined probabilities based upon delivered encoded data. Such methods work well when the probabilities of the symbols are uniformly distributed and different from the predetermined probabilities, but perform worse with predetermined probabilities based upon the delivered encoded data than without it, in cases when the symbols in the data set are not uniformly distributed.